/*
 * File: maze.c
 * ------------
 * This program solves a maze by recursive backtracking.
 */

#include <stdio.h>
#include "genlib.h"
#include "graphics.h"
#include "mazelib.h"
#include "simpio.h"

/*
 * Constants
 * ---------
 * MazeFile -- Name of the file containing the maze
 */

//#define MazeFile "pathlen.maz"


/* Private function prototypes */

bool SolveMaze(pointT pt);
bool SolveMaze2(pointT pt);
static pointT AdjacentPoint(pointT pt, directionT dir);
int ShortestPathLength(pointT pt);

static int counter = 0;

/* Main program */

main() {
	string mazefile = "";

	printf("Input mazefile: \n");
	mazefile = GetLine();
    InitGraphics();
	SetPauseTime(0);
	ReadMazeMap(mazefile);
	SolveMaze(GetStartPosition());
	printf("Number of recursive calls with mark: %d\n", counter);
	counter = 0;
	ReadMazeMap(mazefile);
	SolveMaze2(GetStartPosition());
	printf("Number of recursive calls without unmark: %d\n", counter);
	
}

static bool SolveMaze(pointT pt)
{
    directionT dir;

    if (OutsideMaze(pt)) return (TRUE);
    if (IsMarked(pt)) return (FALSE);
    MarkSquare(pt);
    for (dir = North; dir <= West; dir++) {
        if (!WallExists(pt, dir)) {		
			counter++;
            if (SolveMaze(AdjacentPoint(pt, dir))) {
                return (TRUE);
            }
        }
    }
    UnmarkSquare(pt);
    return (FALSE);
}

static bool SolveMaze2(pointT pt)
{
    directionT dir;

    if (OutsideMaze(pt)) return (TRUE);
    if (IsMarked(pt)) return (FALSE);
    MarkSquare(pt);
    for (dir = North; dir <= West; dir++) {
        if (!WallExists(pt, dir)) {		
			counter++;
            if (SolveMaze2(AdjacentPoint(pt, dir))) {
                return (TRUE);
            }
        }
    }
    //UnmarkSquare(pt);
    return (FALSE);
}



/*
 * Function: AdjacentPoint
 * Usage: newpt = AdjacentPoint(pt, dir);
 * --------------------------------------
 * This function returns the pointT that results from moving
 * one square from pt in the direction specified by dir.  For
 * example, if pt is the point (1,1), AdjacentPoint(pt, East)
 * would return the point (2,1).
 */

static pointT AdjacentPoint(pointT pt, directionT dir)
{
    pointT newpt;

    newpt = pt;
    switch (dir) {
      case North: newpt.y++; break;
      case East:  newpt.x++; break;
      case South: newpt.y--; break;
      case West:  newpt.x--; break;;
    }
    return (newpt);
}
